package com.LeeCode;

/**
 * 摘水果
 */

public class Code2106 {
    public static void main(String[] args) {
        int[][] fruits = {
                {0, 3}, {6, 4}, {8, 5}
        };
        int startPos = 3, k = 2;
        System.out.println(new Code2106().maxTotalFruits(fruits, startPos, k));
    }


    public int maxTotalFruits(int[][] fruits, int startPos, int k) {
        int n = fruits.length;
        // 前缀和数组，preSum[i]表示前i个位置的水果总数
        int[] preSum = new int[n + 1];
        // 计算前缀和
        for (int i = 0; i < n; i++) {
            preSum[i + 1] = preSum[i] + fruits[i][1];
        }

        int ans = 0; // 记录最大水果数

        // 滑动窗口：left和right表示当前考虑的窗口边界
        for (int left = 0, right = 0; right < n; right++) {
            // 调整左边界，直到窗口内的移动步数不超过k
            while (left <= right && !check(fruits[left][0], fruits[right][0], startPos, k)) {
                left++;
            }
            // 更新最大水果数
            ans = Math.max(ans, preSum[right + 1] - preSum[left]);
        }
        return ans;
    }


    //检查从startPos到窗口[leftPos, rightPos]的移动步数是否不超过k
    private boolean check(int leftPos, int rightPos, int startPos, int k) {
        // 情况1：起始位置在窗口左侧
        if (startPos <= leftPos) {
            return rightPos - startPos <= k; // 只需计算到右边界的步数
        }
        // 情况2：起始位置在窗口右侧
        else if (startPos >= rightPos) {
            return startPos - leftPos <= k; // 只需计算到左边界的步数
        }
        // 情况3：起始位置在窗口中间
        else {
            int leftDist = startPos - leftPos; // 到左边界的距离
            int rightDist = rightPos - startPos; // 到右边界的距离
            // 计算总步数：最小距离的往返（2倍）加上最大距离的单程
            int total = 2 * Math.min(leftDist, rightDist) + Math.max(leftDist, rightDist);
            return total <= k;
        }
    }
}
